package com.datastructures.sort;

/**
 * @author MaoLin Wang
 * @date 2019/10/2919:17
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr =new int[100000];
        for (int i=0;i<100000;i++){
            arr[i]=(int)(Math.random()*100000);
        }

        long begintime=System.currentTimeMillis();
        System.out.println("开始时间"+begintime);

        int[] temp=new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);

        long endtime=System.currentTimeMillis();
        System.out.println("结束时间"+endtime);
        System.out.println("用时："+(endtime-begintime)+"ms");

       //int arr[] = {10,4,8,7,1,3,2};


        //System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if (left < right){
            int mid= (left + right ) / 2;
            //向左递归分解
            mergeSort(arr,left,mid,temp);
            //向右递归分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,right,mid,temp);
        }
    }
    /**
     *
     * @param arr 待排序数组
     * @param left 左边有序序列的初始索引
     * @param right 右边索引
     * @param mid
     * @param temp 临时数组
     */
    public static void merge(int[] arr,int left, int right,int mid,int[] temp){
        int l = left; //初始化i，左边有序序列的初始索引
        int r = mid+1; //右边有序序列的初始索引

        int current = 0; // 指向临时数组的当前索引

        //1.先把左边两边的有序数据按规则填充到临时数组，直到任意一方处理完毕

        while ( l<= mid && r <= right){
            if (arr[l] <= arr[r]){
                //当前左边的元素小于等于右边的，将左边的数据拷贝到临时数组
                temp[current] = arr[l];
                current +=1; //current后移
                l +=1; //左边指针右移
            }else {
                //右边的元素移到临时数组
                temp[current] = arr[r];
                current += 1;
                r +=1;
            }
        }
        //2.将有剩余的一边全部移动到临时数组
        while ( l <= mid){//左边有剩余
            temp[current] = arr[l];
            current+=1;
            l+=1;
        }
        while ( r <= right){//右边有剩余
            temp[current] = arr[r];
            current+=1;
            r+=1;
        }
        //3.将临时数组拷贝到原始数组
        current = 0;
        int tempLeft=left;
        while (tempLeft <= right){
            arr[tempLeft] = temp[current];
            current+=1;
            tempLeft +=1;
        }
    }
}
